#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=500000;

void read(int &ret) {
    ret=0;
    static char c;
    for (c=getchar(); c<'0' || c>'9'; c=getchar());
    for (; c>='0' && c<='9'; c=getchar()) ret = ret*10+c-'0';
}

struct SegmentTree {
    int lv[4*maxn+1][3], rv[4*maxn+1][3], lc[4*maxn+1], rc[4*maxn+1], v[4*maxn+1], tag[4*maxn+1];

    void init(int o, int l, int r, int a[]) {
        tag[o] = -1;
        if (l==r) {
            lc[o] = rc[o] = a[l];
            lv[o][0] = rv[o][0] = -1;
        } else {
            int mid=(l+r)/2;
            init(o*2, l, mid, a);
            init(o*2+1, mid+1, r, a);
            pushUp(o, l, r);
        }
    }

    void pushDown(int o, int l, int r) {
        if (tag[o]>=0) {
            v[o] = 0;
            lc[o] = rc[o] = tag[o];
            if (l!=r) {
                lv[o][0] = rv[o][0] = tag[o];
                lv[o][1] = rv[o][1] = l;
                lv[o][2] = rv[o][2] = r;
                tag[o*2] = tag[o*2+1] = tag[o];
            }
            tag[o] = -1;
        }
    }

    void pushUp(int o, int l, int r) {
        int mid=(l+r)/2, x=o*2, y=o*2+1;
        v[o] = max(v[x], v[y]);
        if (lv[y][0]>=0 && rv[x][0]>=0) {
            if (rc[x]!=lc[y]) v[o] = max(v[o], (lv[y][1]-rv[x][2])/2);
            else {
                v[o] = max(v[o], max(mid-rv[x][2], lv[y][1]-mid-1)/2);
            }
        }
        lc[o] = lc[x], rc[o] = rc[y];

        if (lv[x][0]>=0) {
            lv[o][0] = lv[x][0];
            lv[o][1] = lv[x][1];
            if (lv[x][2]==mid && lv[x][0]==lc[y]) {
                if (lv[y][1]==mid+1) {
                    lv[o][2] = lv[y][2];
                } else lv[o][2] = mid+1;
            } else lv[o][2] = lv[x][2];
        } else {
            if (rc[x]==lc[y]) {
                lv[o][0] = rc[x];
                lv[o][1] = mid, lv[o][2] = mid+1;
            } else {
                lv[o][0]=lv[y][0];
                lv[o][1]=lv[y][1], lv[o][2]=lv[y][2];
            }
        }

        if (rv[y][0]>=0) {
            rv[o][0] = rv[y][0];
            rv[o][2] = rv[y][2];
            if (rv[y][1]==mid+1 && rc[x]==rv[y][0]) {
                if (rv[x][2]==mid+1) {
                    rv[o][1] = rv[x][1];
                } else rv[o][1] = mid;
            } else rv[o][1] = rv[y][1];
        } else {
            if (rc[x]==lc[y]) {
                rv[o][0] = rc[x];
                rv[o][1] = mid, rv[o][2] = mid+1;
            } else {
                rv[o][0] = rv[x][0];
                rv[o][1] = rv[x][1], rv[o][2] = rv[x][2];
            }
        }
    }

    void set(int o, int l, int r, int tl, int tr, int tv) {
        pushDown(o, l, r);
        if (l==tl && r==tr) {
            tag[o] = tv;
            pushDown(o, l, r);
        } else {
            int mid=(l+r)/2;
            if (tl<=mid) set(o*2, l, mid, tl, min(tr, mid), tv);
            else pushDown(o*2, l, mid);
            if (tr>mid) set(o*2+1, mid+1, r, max(tl, mid+1), tr, tv);
            else pushDown(o*2+1, mid+1, r);
            pushUp(o, l, r);
        }
    }
};

int main() {
    freopen("transform.in", "r", stdin);
    freopen("transform.out", "w", stdout);

    static SegmentTree sgt;
    static int a[maxn+1];
    int n, q;
    read(n);read(q);
    scanf(" ");
    for (int i=1; i<=n; i++)  a[i]=getchar()-'0';
    sgt.init(1, 1, n, a);

    for (int i=1; i<=q; i++) {
        int l, s, k;
        read(s);read(l);read(k);
        if (s+l<=n) sgt.set(1, 1, n, s+1, s+l, k);
        else {
            sgt.set(1, 1, n, s+1, n, k);
            sgt.set(1, 1, n, 1, s+l-n, k);
        }

        int ans=sgt.v[1];
        if (sgt.lc[1]!=sgt.rc[1]) {
            ans=max(ans, (sgt.lv[1][1]+n-sgt.rv[1][2])/2);
            if (sgt.lv[1][2]<=sgt.lv[1][1]) ans=-1;
        } else {
            if (sgt.lv[1][1]==1) {
                if (sgt.rv[1][2]<n) {
                    ans = max(ans, (n-sgt.rv[1][2])/2);
                }
            } else {
                ans = max(ans, (sgt.lv[1][1]-1)/2);
            }
            if (sgt.rv[1][2]==n) {
                if (sgt.lv[1][1]>1) {
                    ans = max(ans, (sgt.lv[1][1]-1)/2);
                }
            } else {
                ans = max(ans, (n-sgt.rv[1][2])/2);
            }
            if (sgt.lv[1][0]==-1 && sgt.rv[1][0]==-1) {
                ans = max(ans, (n-1)/2);
            }
        }
        printf("%d\n", ans);
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}
